#include "big_int.h"

big_int::big_int()
{

}
big_int::big_int(string str_in)
{
	string temp;
	size_t i;
	for (i = str_in.length(); i >= digits; i -= digits)
	{
		temp = str_in.substr(i - digits, digits);
		numb.push_back(string_into_longlong(temp));
	}
	if (i != 0)
	{
		temp = str_in.substr(0, i);
		numb.push_back(string_into_longlong(temp));
	}
}
big_int::big_int(const big_int& a)
{
	numb = a.numb;
}
int big_int::length() const 
{
	return numb.size();
}
long long big_int::comp (const big_int &b)
{
	if (length() != b.length())
		return length() - b.length();
	for (int i = length() - 1; i >= 0; i--)
	{
		if (numb[i] != b.numb[i])
		{
			return numb[i] - b.numb[i];
		}
	}
	return 0;
}
long long big_int::string_into_longlong(const string &s)
{
	int length;
	int temp_int = 0;
	if (digits < s.length())
		length = digits;
	else
		length = s.length();
	for (int j = 0; j < length; j++)
		temp_int = temp_int * 10 + s[j] - '0';
	return temp_int;
}
long long& big_int::operator [] (int i)
{
	return numb[i];
}
big_int big_int::operator - (const big_int &a)
{
	big_int result = *this;
	for (int i = 0; i < a.length(); i++)
	{
		result[i] -= a.numb[i];
		if (result.numb[i] < 0)
		{
			result[i] += base;
			result[i + 1]--;
		}
	}
	int pos = result.length()-1;
	while ((pos > 0) && !result.numb[pos])
		pos--;
	result.numb.resize(pos+1);
	return result;
}
big_int big_int::operator * (const int &n)
{
	big_int outcome;
	outcome.numb.resize(length() + 1);
	numb.resize(length() + 1);
	long long r = 0;
	for (int i = 0; (i < outcome.length()) || (r != 0); i++)
	{
		outcome[i] = abs(numb[i] * n) + r;
		r = outcome[i] / base;
		outcome[i] -= r * base;
	}
	while ((outcome.length() > 0) && (!outcome[outcome.length() - 1]))
		outcome.numb.resize(outcome.length() - 1);
	numb.resize(length() - 1);
	return outcome;
}
pair<big_int, big_int> big_int::operator / (const big_int &a)
{
	big_int outcome;
	big_int present;
	outcome.numb.resize(length());
	big_int divisor = a;
	for (int i = length() - 1; i >= 0; --i)
	{
		present.numb.resize(present.length() + 1);
		for (int j = present.length() - 1; j >= 1; j--)
			present[j]=present[j - 1];
		present[0] = numb[i];
		if (present.zero())
			break;
		int pos = present.length() - 1;
		while (pos > 0 && !present[pos])
			pos--;
		present.numb.resize(pos + 1);
		int x = 0, l = 0, r = base;
		while (l <= r)
		{
			int m = (l + r) >> 1;
			big_int c = divisor * m;
			if (c <= present)
			{
				x = m;
				l = m + 1;
			} else
				r = m - 1;
		}
		outcome[i] = x;
		big_int dif = divisor * x;
		present = present - dif;
	}
	int pos = outcome.length() - 1;
	while (pos > 0 && !outcome[pos])
		pos--;
	outcome.numb.resize(pos + 1);
	pos = present.length() - 1;
	while (pos > 0 && !present[pos])
		pos--;
	present.numb.resize(pos + 1);
	return std::make_pair(outcome, present);
}
bool big_int::zero()
{
	int l = length();
	for (int i = 0; i < l; i++)
	{
		if (numb[i] != 0)
		{
			return false;
		}
	}
	return true;
}
bool big_int::operator > (const big_int &b)
{
	return (comp(b) > 0);
}
bool big_int::operator < (const big_int &b)
{
	return (comp(b) < 0);
}
bool big_int::operator == (const big_int &b)
{
	return (comp(b) == 0);
}
bool big_int::operator <= (const big_int &b)
{
	return (comp(b) <= 0);
}
bool big_int::operator >= (const big_int &b)
{
	return (comp(b) >= 0);
}
string big_int::to_string()
{
	string result = "";
	result += longlong_into_string(numb.back());
	for (int i = length() - 2; i >= 0; i--)
	{
		string temp = longlong_into_string(numb[i]);
		for (int j = temp.length(); j < digits; j++)
		{
			result += '0';
		}
		result += temp;
	}
	return result;
}
string big_int::longlong_into_string(const long long &a)
{
	if (a == 0)
		return "0";
	string temp = "";
	long long temp_int = a;
	while (temp_int > 0)
	{
		temp += temp_int % 10 + '0';
		temp_int /= 10;
	}
	reverse(temp.begin(), temp.end());
	return temp;
}